package ljl.codetop2;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * todo 过几天再看看，这个题有点东西的
 */
public class _139_word_break {

    /**
     * todo 忘的一干二净有点难受，兄弟
     */
    static class a {
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> wordDictSet = new HashSet<>(wordDict);
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }

    static class off1 {
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> d = new HashSet<>(wordDict);
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (dp[j] && d.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }

    /*
     * dfs 和 bfs 都是暴力法，不过使用了 visited 记录中间结果，避免了重复计算，比 dp 还快
     * 所以有时一个小缓存能起到惊人的作用
     */

    /**
     * bfs 比 dp 快
     */
    static class biyou1 {
        public boolean wordBreak(String s, List<String> wordDict) {
            LinkedList<Integer> queue = new LinkedList<>();
            queue.add(0);

            int slength = s.length();
            boolean[] visited = new boolean[slength + 1];

            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int start = queue.poll();
                    for (String word : wordDict) {
                        int nextStart = start + word.length();
                        if (nextStart > slength || visited[nextStart]) {
                            continue;
                        }

                        if (s.indexOf(word, start) == start) {
                            if (nextStart == slength) {
                                return true;
                            }

                            queue.add(nextStart);
                            visited[nextStart] = true;
                        }
                    }
                }
            }

            return false;
        }
    }

    static class copy_biyou1 {
        public boolean wordBreak(String s, List<String> wordDict) {
            LinkedList<Integer> q = new LinkedList<>();
            q.offer(0);
            boolean[] vis = new boolean[s.length() + 1];
            while (!q.isEmpty()) {
                int start = q.poll();
                for (String word : wordDict) {
                    int next = start + word.length();
                    if (next > s.length() || vis[next]) continue;
                    if (s.indexOf(word, start) == start) {
                        if (next == s.length())
                            return true;
                        vis[next] = true;
                        q.offer(next);
                    }
                }
            }
            return false;
        }
    }

    /**
     * 怎么都看不出来这个解法快
     * 但它是最快的
     *
     * todo 想不明白它为什么这么快
     */
    static class biyou2 {
        public boolean wordBreak(String s, List<String> wordDict) {
            return dfs(s, 0, wordDict, new boolean[s.length() + 1]);
        }
        private boolean dfs(String s, int start, List<String> wordDict, boolean[] visited) {
            for (String word : wordDict) {
                int nextStart = start + word.length();
                if (nextStart > s.length() || visited[nextStart]) {
                    continue;
                }

                if (s.indexOf(word, start) == start) {
                    if (nextStart == s.length() || dfs(s, nextStart, wordDict, visited)) {
                        return true;
                    }
                    visited[nextStart] = true;
                }
            }
            return false;
        }
    }

    static class copy_biyou2 {
        public boolean wordBreak(String s, List<String> wordDict) {
            return dfs(s, wordDict, 0, new boolean[s.length() + 1]);
        }
        boolean dfs(String s, List<String> wordDict, int start, boolean[] vis) {
            for (String word : wordDict) {
                int next = start + word.length();
                if (next > s.length() || vis[next]) continue;
                if (s.indexOf(word, start) == start) {
                    if (next == s.length() || dfs(s, wordDict, next, vis))
                        return true;
                    vis[next] = true;
                }
            }
            return false;
        }
    }
}
